package previous.Test_0223;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //最长公共前缀
    //解法一：
    public String longestCommonPrefix1(String[] strs) {
           String s1=strs[0];
           //两两进行比较
        int j=0;
        for (int i = 1; i <strs.length ; i++) {
            String ret=strs[i];
            s1=find(s1,ret);
        }
       return s1;
    }
    public String find(String s1,String ret){
        int i=0;
        while(i<Math.min(s1.length(),ret.length() )&& s1.charAt(i) ==ret.charAt(i)){
            i++;
        }
        return s1.substring(0,i);
    }
    //解法二
    public String longestCommonPrefix(String[] strs) {
          String s1=strs[0];
        char[] ch=s1.toCharArray();
        for (int i = 0; i < s1.length(); i++) {
            char c=ch[i];
            for (int j = 1; j < strs.length; j++) {
                //如果不相等，返回
                if(i!=strs[j].length() || c!=strs[j].charAt(i)){
                    return s1.substring(0,i);
                }
            }
        }
        return s1;
    }
    //最长回文串
    public String longestPalindrome(String s) {
         int n=s.length();
         int left=0,right=0;
         int begin=0,len=0;
        for (int i = 0; i <n ; i++) {
            //奇数
            left=i;
            right=i;
            while(left>=0 && right<n && s.charAt(left)==s.charAt(right)){
            left++;
            right--;
            }
            if(right-left-1>0){
                begin=left+1;
                len=right-left-1;
            }
            //偶数
            left=i;
            right=i+1;
            while(left>=0 && right<n && s.charAt(left)==s.charAt(right)){
                left++;
                right--;
            }
            if(right-left-1>0){
                begin=left+1;
                len=right-left-1;
            }
        }
        return s.substring(begin,begin+len);
        }
        //第n个泰波那锲数
    public int tribonacci(int n) {
        int[] dp=new int[n];
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        int i=0;
        for ( i = 3; i <=n ; i++) {
            dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
        }
        return dp[i];
    }
}
